#include<stdio.h>
#include<iostream>

using namespace std;

typedef struct node {
    char data;
    struct node* left, * right;
} BTree;

// 创建新节点的函数
BTree* createNode(char data) {
    BTree* newNode = (BTree*)malloc(sizeof(BTree));  // 分配内存

    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);  // 如果分配失败，退出程序
    }

    newNode->data = data;   // 直接赋值字符
    newNode->left = NULL;   // 初始化左子树为空
    newNode->right = NULL;  // 初始化右子树为空

    return newNode;  // 返回新创建的节点
}

void PrintS(BTree* root, int cnt) {
    if (!root) return;                              //为空时返回
    if((root->left || root->right) && cnt != 0)     //存在左子树或右子树时该节点为运算符号应加上括号
        cout << "(";                                //当为根节点（cnt == 0）时无需加，即无需在整个式子外加括号
    PrintS(root->left, cnt+1);                      //左子树
    cout << root->data;                             //中序遍历
    PrintS(root->right, cnt+1);                     //右子树
    if ((root->left || root->right) && cnt != 0)
        cout << ")";
}

int main() {
    //树1
    BTree* root1 = createNode('*');
    BTree* a2 = createNode('+');
    BTree* a3 = createNode('*');
    BTree* a4 = createNode('a');
    BTree* a5 = createNode('b');
    BTree* a6 = createNode('c');
    BTree* a7 = createNode('-');
    BTree* a8 = createNode('d');

    root1->left = a2; root1->right = a3;
    a2->left = a4; a2->right = a5;
    a3->left = a6; a3->right = a7;
    a7->right = a8;

    //树2
    BTree* root2 = createNode('+');
    BTree* b2 = createNode('*');
    BTree* b3 = createNode('-');
    BTree* b4 = createNode('a');
    BTree* b5 = createNode('b');
    BTree* b6 = createNode('-');
    BTree* b7 = createNode('c');
    BTree* b8 = createNode('d');

    root2->left = b2; root2->right = b3;
    b2->left = b4; b2->right = b5;
    b3->right = b6;
    b6->left = b7; b6->right = b8;

    PrintS(root1, 0);
    cout << endl;
    PrintS(root2, 0);
    return 0;
}